package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组  nums  中。
 * <p>
 * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得  nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
 * 这里的 i - 1 和 i + 1 代表和  i  相邻的两个气球的序号。
 * 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
 * <p>
 * 求所能获得硬币的最大数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/burst-balloons
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/27 11:46
 */
public class maxCoins {
    // 视频题解：https://leetcode-cn.com/problems/burst-balloons/solution/312-chuo-qi-qiu-dong-tai-gui-hua-by-chen-1sre/
    // 文字题解：https://leetcode-cn.com/problems/burst-balloons/solution/zhe-ge-cai-pu-zi-ji-zai-jia-ye-neng-zuo-guan-jian-/
    // dp 状态定义：dp[i][j] 表示 数组val (i,j)  开区间内获得硬币的最大数量
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // dp[]
        int[][] dp = new int[n + 2][n + 2];
        int[] val = new int[n + 2];
        val[0] = val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        // n-1  n  n+1
        // 用下标不断递减，来扩大区间，i区间左下标
        for (int i = n - 1; i >= 0; i--) {
            // j 表示 区间右下标
            for (int j = i + 2; j <= n + 1; j++) {
                // k 表示区间内最后一个戳破的气球位置。
                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += dp[i][k] + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], sum);
                }
            }
        }
        return dp[0][n + 1];
    }
}
